// 搜索
let arr = [1,2,3,5,6]

function search(arr, val) {
  for(let i = 0; i< arr.length; i++) {
    let item = arr[i]
    if(item == val){
      return i;
    }
  }
  return -1;
}
// console.log(search(arr, 3))


// 二分查找
function binarySearch(arr, val) {
  let low = 0
  let high = arr.length
  while(low<high) {
    let mid = ~~((low+high)/2)
    if(arr[mid] == val) {
      return mid
    }else if(arr[mid] > val) {
      high = mid
    }else{
      low = mid
    }
  }
  return -1
}
console.log(binarySearch([1,2,3,4,5,6,7], 1))


function ListNode(val, next) {
      this.val = (val===undefined ? 0 : val)
     this.next = (next===undefined ? null : next)
}

var mergeTwoLists = function(l1, l2) {
  if (l1 === null) {
      return l2;
  } else if (l2 === null) {
      return l1;
  } else if (l1.val < l2.val) {
      l1.next = mergeTwoLists(l1.next, l2);
      return l1;
  } else {
      l2.next = mergeTwoLists(l1, l2.next);
      return l2;
  }
}
let l1 = new ListNode(1)
l1.next = new ListNode(2)
l1.next.next = new ListNode(4)

let l2 = new ListNode(1)
l2.next = new ListNode(3)
l2.next.next = new ListNode(4)

mergeTwoLists(l1, l2)